/*
 * @lc app=leetcode.cn id=435 lang=typescript
 *
 * [435] 无重叠区间
 * 在按照结尾排序时，开始的位置变得不重要了
 * 因为在总体的空间里，占用右侧空间最小的一定最优
 */

// @lc code=start
function eraseOverlapIntervals(intervals: number[][]): number {
    intervals.sort((a, b) => a[1] - b[1])

    const n = intervals.length

    let removed = 0, prev = intervals[0][1]

    for (let i = 1; i < n; i++) {
        // 如果第二个的左边小于第一个的右边，那么就有重叠
        // 移除第二个，因为第二个占用空间一定更大，成本更高
        if (intervals[i][0] < prev) {
            removed += 1
        }
        else {
            prev = intervals[i][1]
        }
    }

    return removed
};
// @lc code=end

console.log(
    // eraseOverlapIntervals([[1,2],[2,3],[3,4],[1,3]]) // 1
    // eraseOverlapIntervals([ [1,2], [1,2], [1,2] ]) // 2
    // eraseOverlapIntervals([ [1,2], [2,3] ]) // 0
)